package dataStructures.list;

import java.util.Iterator;

/**
 *
 * An implementation of an unrolled linked list.
 * 
 * Fully Tested: No
 * Fully Documented: No
 * Created: 22-Nov-2011
 * Last Updated: 22-Nov-2011
 *
 * @author Shimu Wu
 */
public class SinglelyLinkedArray<T> implements Iterable<T> {

    private final static byte ARRAY_SIZE = 10;

    /** The size of the linked array */
    private int size;

    private LinkedArray<T> first, last;

    public SinglelyLinkedArray() {
        this.size = 0;
        this.first = new LinkedArray<T>(ARRAY_SIZE);
        this.last = first;
    }

    /*
    public SinglelyLinkedNode<T> getFirst() {
    return this.first;
    }
     *
     */
    /*
     * Adds an item to the front of the LinkedList.
     * @param data
    
    public void addFirst(T data) {
    SinglelyLinkedNode<T> oldFirst = first;
    first = new SinglelyLinkedNode<T>(data, oldFirst);
    size++;
    }
     */
    /**
     * Returns and removes an item from the front of the LinkedList.
     * Returns null if the item at the front of the LinkedList is null or
     * if the LinkedList is empty.
     *
     * @return the item at the front of the LinkedList
    
    public T removeFirst() {
    if (first == null) {
    return null;
    } else {
    T returnData = first.data;
    first = first.next;
    size--;
    if (first == null) {
    last = null;
    }
    return returnData;
    }
    }
     */
    /**
     * Returns true if this LinkedList has no more elements, false otherwise.
     * @return true if this LinkedList is empty.
     */
    public boolean isEmpty() {
        return (size == 0);
    }

    /**
     * Returns the number of elements in this LinkedList.
     * @return the size of this LinkedList.
     */
    public int getSize() {
        return this.size;
    }

    /**
     * Adds an element to the end of the SinglelyLinkedArray
     * @param element
     */
    public void addLast(T element) {
        if (last.size < last.MAX_SIZE) {
            last.addLast(element);
        } else {
            LinkedArray<T> newLinkedArray = new LinkedArray<T>(ARRAY_SIZE);
            newLinkedArray.addLast(element);
            last.next = newLinkedArray;
            last = newLinkedArray;
        }
        size++;
    }
    
    public void remove(Remover<T> remover){
        
    }

    /**
     * Prints the content of this SinglelyLinkedArray, one element per
     * line.
     */
    public void printContent() {
        System.out.println("-------------- List Content --------------");
        for (T element : this) {
            System.out.println(element);
        }
        System.out.println("------------------------------------------");
    }

    /**
     * For storage purposes, puts all the content of this SinglelyLinkedArray
     * into one LinkedArray, runs in O(n), should only be called when there
     * is spare time in the CPU.
     */
    public void optimize() {
        LinkedArray<T> newLinkedArray = new LinkedArray<T>((byte)size);
        for (T item : this) {
            newLinkedArray.addLast(item);
        }
        removeReferences();
        first = newLinkedArray;
        last = first;
    }

    /** 
     * Starting at the first LinkedArray, go through each LinkedArray and
     * set the next pointer to null.
     */
    private void removeReferences() {
        LinkedArray<T> current, next;
        current = first;
        while (current != null) {
            next = current.next;
            current.next = null;
            current = next;
        }
    }

    public Iterator<T> iterator() {

        class LinkedArrayIterator implements Iterator<T> {

            /** A pointer to the current LinkedArray in the iteration */
            private LinkedArray<T> current;

            /** The index of the current object in the current LinkedArray*/
            private int index;

            LinkedArrayIterator() {
                current = first;
                index = 0;
            }

            public boolean hasNext() {
                return (current != null);
            }

            @SuppressWarnings("unchecked")
            public T next() {
                T returnVal = (T) current.data[index];
                index++;
                if (index == current.size) {
                    index = 0;
                    current = current.next;
                }
                return returnVal;
            }

            public void remove() {
            }
        }

        return new LinkedArrayIterator();
    }

    private static class LinkedArray<T> {

        /** An array to store data */
        private Object[] data;

        private final byte MAX_SIZE;

        /** The number of elements stored in the data array */
        private byte size;

        /** A pointer to the next LinkedArray */
        private LinkedArray<T> next;

        private LinkedArray(byte MAX_SIZE) {
            this.MAX_SIZE = MAX_SIZE;
            data = new Object[MAX_SIZE];
            size = 0;
            next = null;
        }

        /**
         * Adds the given element to the LinkedArray, returns true if the
         * addition of the element was successful. Returns false if this
         * LinkedArray is full.
         * 
         * @param element
         * @return
         */
        private void addLast(T element) {
            data[size] = element;
            size++;
        }
    }
}
